#include "../common.h"
class Solution {
private:
    vector<vector<string>> ret;
    vector<string> part ;
public:
    vector<vector<string>> solveNQueens(int n) {
        part.assign(n, string(n, '.'));
        vector<uint8_t> col(n), diag1(n * 2 - 1), diag2(n * 2 - 1); // uint8_t 效率比 bool 快
        dfs(0,col,diag1,diag2);
        return ret;
    }
    void dfs(int row, vector<uint8_t>& col, vector<uint8_t>& diag1, vector<uint8_t>& diag2){
        // 递归出口
        if(row == col.size()){
            ret.push_back(part);
        }
        for(int c = 0; c < col.size(); ++c){
            int rc = row - c + col.size() - 1;//反斜线
            if(!col[c] && !diag1[row + c] && !diag2[rc]){
                part[row][c] = 'Q';
                col[c] = diag1[row + c] = diag2[rc] = true;
                dfs(row + 1, col, diag1, diag2);
                col[c] = diag1[row + c] = diag2[rc] = false;
                part[row][c] = '.';
            }
        }
    }
};